Online-Academy

Look, Read, Understand, Apply

Menu

Data Structure

Binary Search Tree

Binary Search Tree (BST)

Binary Search Tree is a tree in which each node can have only 0, 1, or 2 children. Nodes in the left of root is less than root node and nodes in the right of the root is greater than root node. This rule is same for the sub trees also.
BST can be traversal in following ways:

  • Preorder: First visit root node, then left child, then right child
  • Inorder: First visit left child, then root node, then right child. This traversal displays node in ascending order.
  • Post Order: First visit left child, then right child, the root.

If the left subtree or right subtree of the BST is lengthy compared to each other, then searching in the lengthy subtree will take more time than shorter subtree. The height of left and right subtrees are not balanced in the BST. This creates long search time for the lengthy subtree. 

import java.util.*;
class node{
    int data;
    node left,right;
    public node(int d){
        data = d;
        left = right = null;
    }
}
class binary_tree{
    node root=null;
    node temp;
    public void insertNode(node n){
        if(root ==null){
            root = n;
        }else{
            temp = root;
            while(temp!=null){
                if(temp.data>n.data){
                    if(temp.left == null){
                        temp.left = n;
                        break;
                    }else
                    temp = temp.left;
                }
                else if(temp.data <=n.data){
                    if(temp.right == null){
                        temp.right = n;
                        break;
                    }else
                    temp = temp.right;
                }
            }
        }
    }
    public void inorder(node r){
        if(r!=null){
            inorder(r.left);
            System.out.println(" "+r.data);
            inorder(r.right);
        }
    }
    public node getRoot(){
        return root;
    }
}
class binary_tree_demo{
    public static void main(String[] args){
        node temp;
        Scanner sc = new Scanner(System.in);
        int option,value;
        binary_tree bt = new binary_tree();
        while(true){
            System.out.println("\n1.InsertNode\n2.DisplayTree\n8.Exit");
            option = sc.nextInt();
            switch(option){
                case 1:System.out.println("Enter a value:");
                    value = sc.nextInt();
                    temp = new node(value);
                    bt.insertNode(temp);
                break;
                case 2: System.out.println("Display Tree:");
                    bt.inorder(bt.getRoot());
                break;
                case 8:System.exit(0);
            }
        }
    }
}